package com.lw.leetcode.sort.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 1387. 将整数按权重排序
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/27 21:06
 */
public class GetKth {

    public static void main(String[] args) {
        GetKth test = new GetKth();

        // 13
        int a = 12;
        int b = 15;
        int c = 2;

        // 7
//        int a = 7;
//        int b = 11;
//        int c = 4;

        // 13
//        int a = 10;
//        int b = 20;
//        int c = 5;

        // 570
//        int a = 1;
//        int b = 1000;
//        int c = 777;

        int kth = test.getKth(a, b, c);
        System.out.println(kth);
    }

    private Map<Integer, Integer> map = new HashMap<>();

    public int getKth(int lo, int hi, int k) {
        map.put(1, 0);
        int size = hi - lo + 1;
        int[] arr = new int[size];
        for (int i = lo; i <= hi; i++) {
            int c = find(i);
            arr[i - lo] = (c << 10) + i;
        }
        Arrays.sort(arr);
        return arr[k - 1] & 0X3FF;
    }

    private int find(int key) {
        Integer v = map.get(key);
        if (v != null) {
            return v;
        }
        v = ((key & 1) == 0 ? find(key >> 1) : find(3 * key + 1)) + 1;
        map.put(key, v);
        return v;
    }

}
